#define DEBUG
#include <cstdio>
#include <cmath>

using namespace std;

typedef long long ll;
const int sqrtn=31623, maxs=1000000;

ll f0(ll n, int p, int sn) {
  return n%p;
}

ll f1(ll n, int p, int sn) {
  static ll s[sqrtn+1];
  if (n<=sn) {
    if (s[n]) return s[n];
    else return s[n] = n*(n+1)/2%p;
  } else return n*(n+1)/2%p;
}

ll f2(ll n, int p, int sn) {
  static ll s[sqrtn+1];
  if (n<=sn && s[n]) return s[n];
  ll a=n, b=n+1, c=2*n+1;
  if (a%2==0) a/=2;
  else b/=2;
  if (a%3==0) a/=3;
  else if (b%3==0) b/=3;
  else c/=3;
  if (n<=sn) return s[n] = a*b%p*c%p;
  return a*b%p*c%p;
}

ll f3(ll n, int p, int sn) {
  static ll s[sqrtn+1];
  if (n<=sn && s[n]) return s[n];
  ll t=n*(n+1)/2%p;
  if (n<=sn) return s[n] = t*t%p;
  return t*t%p;
}

ll getSum(int o, int n, int sn, int p, ll s[][2], ll g(ll n, int p, int sn), ll h(ll n, int p, int sn), ll pre[]) {
  if (o<=maxs) return pre[o];
  if (o<=sn && s[o][0]) return s[o][0];
  if (o>sn && s[n/o][1]) return s[n/o][1];
  if (o==1) return s[1][0] = 1;
  ll ans=h(o, p, sn);
  for (int i=2; i<=o; i=o/(o/i)+1) {
    ans = (ans+p-(g(o/(o/i), p, sn)+p-g(i-1, p, sn))%p*getSum(o/i, n, sn, p, s, g, h, pre)%p)%p;
  }
  if (o<=sn) s[o][0] = ans;
  else s[n/o][1] = ans;
  return ans;
}

void sieve(int n, ll phi[]) {
  static int pri[maxs+1];
  static bool book[maxs+1];
  phi[1] = 1;
  for (int i=2; i<=n; i++) {
    if (!book[i]) pri[++pri[0]] = i, phi[i]=i-1;
    for (int j=1; j<=pri[0] && i*pri[j]<=n; j++) {
      book[i*pri[j]]=true;
      if (i%pri[j]==0) {
        phi[i*pri[j]] = phi[i]*pri[j];
        break;
      } else phi[i*pri[j]] = phi[i]*phi[pri[j]];
    }
  }
}

int main() {
  freopen("cake.in", "r", stdin);
  freopen("cake.out", "w", stdout);

  static ll s[3][sqrtn+1][2], phi[3][maxs+1];
  int n, p, sn;
  scanf("%d %d", &n, &p);

  sieve(maxs, phi[0]);
  for (int i=1; i<=maxs; i++) {
    phi[1][i] = phi[0][i]*i%p;
    phi[2][i] = phi[1][i]*i%p;
    for (int j=0; j<3; j++) phi[j][i] = (phi[j][i]+phi[j][i-1])%p;
  }

  sn = sqrt(n);
  ll ans=((4LL*n*n%p*(getSum(n, n, sn, p, s[0], f0, f1, phi[0])+p-1)%p+p-
           6LL*n%p*(getSum(n, n, sn, p, s[1], f1, f2, phi[1])+p-1)%p)%p+
          2LL*(getSum(n, n, sn, p, s[2], f2, f3, phi[2])+p-1)%p+
          2LL*(n-1)*(n-1)%p+2LL*n*(n-1)%p)%p;
  printf("%lld", ans);

  fclose(stdin);
  fclose(stdout);
  return 0;
}
